原始题目：剑指 Offer 15. 二进制中1的个数 (opens new window)

解题思路：

首先介绍一个位操作，当 $n \neq 0$ 时，$n$ & $(n-1)$ 会消除掉 $n$ 最右边的 $1$，举个例子：

假设 $n = 1010$，则 $n - 1 = 1001$，$m = n$ & $(n -1 ) = 1000$，$m$ 和 $n$ 的对比之下，是否是 $n$ 最右边的 $1$ 变成了 $0$ 就是 $m$ 了。

$$n = 1010 \\ m = 1000$$

因此，每进行一次上述操作，$n$ 就会消掉一个 $1$，能进上多少次上述操作，说明 $n$ 就有多少个 $1$。

代码：

public int hammingWeight(int n) {
    int c = 0;
    while (n != 0) {
        c++;
        n = n & (n - 1);
    }
    return c;
}

复杂度分析

• 时间复杂度$O(N)$：$N$ 为 $n$ 的二进制 $1$ 的个数。

• 空间复杂度$O(1)$： 变量 $c$ 使用常数大小额外空间。